package com.major.binarysorttree;

public class BinarySortTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public BinarySortTree() {
    }

    public BinarySortTree(Node root) {
        this.root = root;
    }

    // 添加
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 中序遍历
    public void inOrder() {
        if (root != null){
            root.inoOrder();
        }else {
            System.out.println("空树，，，");
        }
    }

    // 删除
    public void delete(int val) {
        // 找到要删除结点
        Node targetNode = search(val);
        if (targetNode == null){
            System.out.println("不存在该结点");
            return;
        }
        // 如果该二叉树只有一个结点
        if (root.getLeftNode() ==null && root.getRightNode() == null){
            root = null;
            return;
        }

        // 找到父结点
        Node parent = searchParent(val);

        // 如果删除叶子结点
        if (targetNode.getLeftNode() == null && targetNode.getRightNode() ==null){
            // 判断是父结点的左子
            if (parent.getLeftNode() != null && parent.getLeftNode().getValue() == val){
                parent.setLeftNode(null);
            // 还是右子
            }else if (parent.getRightNode() != null && parent.getRightNode().getValue() == val){
                parent.setRightNode(null);
            }

        // 删除有两个子结点的结点
        }else if (targetNode.getLeftNode() != null && targetNode.getRightNode() != null){
            // 把当前值换成左子树最大结点的值，，，或者右子树最小结点的值
            int leftTreeMax = deleteLeftMax(targetNode.getLeftNode());
            targetNode.setValue(leftTreeMax);
        }

        // 删除只有一个子结点的结点
        else {
            if (targetNode.getLeftNode() != null){
                int temp = targetNode.getLeftNode().getValue();
                delete(temp);
                targetNode.setValue(temp);
            }else {
                int temp = targetNode.getRightNode().getValue();
                delete(temp);
                targetNode.setValue(temp);
            }
        }
    }

    // 删除有两个子结点的结点
    // 其中
    // 删除左子树最大值的情况
    private int deleteLeftMax(Node leftNode) {
        /*if (leftNode.getRightNode() == null){
            int leftMax = leftNode.getValue();
            delete(leftMax);
            return leftMax;
        }else {

        }*/
        Node leafMax = leftNode;
        // 循环找到最大值
        while (leafMax.getRightNode() != null){
            leafMax = leafMax.getRightNode();
        }
        delete(leafMax.getValue());
        return leafMax.getValue();
    }

    // 找到要删除结点的父结点
    private Node searchParent(int val) {
        if (root == null){
            System.out.println("空树。。。");
            return null;
        }else {
            return root.searchParent(val);
        }
    }

    // 查找到要删除结点
    private Node search(int val) {
        if (root == null){
            return null;
        }else {
            return root.search(val);
        }
    }
}
